#include <iostream>
#include <string.h>
#include <algorithm>
#define N 1010
using std::min;
using namespace std;
int dp[N];
void work(char a[], char b[]) {
    int lena = strlen(a);
    int lenb = strlen(b);
    for(int j=1; j<=lenb; j++) dp[j] = j;
    int t1, t2;
    for(int i=1; i<=lena; i++) {
        t1 = dp[0]++;
        for(int j=1; j<=lenb; j++) {
            t2 = dp[j];
            if(a[i-1]==b[j-1])
                dp[j] = t1;
            else
                dp[j] = min(t1, min(dp[j-1], dp[j]))+1;
            t1 = t2;
        }
    }
    cout<<dp[lenb]<<endl;
}

int main() {
    char a[N],b[N];
    cin>>a>>b;
    work(a,b);
    return 0;
}